/*
 * @Author: 缄默
 * @Date: 2021-11-16 19:07:24
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-30 16:41:15
 */

//换钱的方法数

#include <iostream>
#include <vector>

using namespace std;


int coins1(vector<int>& arr, int aim);
int process1(vector<int>& arr, int level, int aim);
int coins2(vector<int>& arr, int aim); 
int process2(vector<int>& arr, int level, int aim, vector<vector<int>>& map);
int coins3(vector<int>& arr, int aim);
int coins5(vector<int>& arr, int aim);

int main() {
    vector<int> arr({5, 10, 25, 1});
    cout << coins1(arr, 1000) << endl;
    cout << coins2(arr, 1000) << endl;
    cout << coins3(arr, 1000) << endl;
    cout << coins5(arr, 1000) << endl;

    return 0;
}

int coins1(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return 0;
    return process1(arr, 0, aim);
}

int process1(vector<int>& arr, int level, int aim) {
    if (level == arr.size()) return aim == 0;
    int res = 0;
    for (int i = 0; i * arr[level] <= aim; i++) {
        res += process1(arr, level + 1, aim - i * arr[level]);
    }
    return res;
}

int coins2(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return 0;
    vector<vector<int>> map(arr.size() + 1, vector<int>(aim + 1, 0));
    return process2(arr, 0, aim, map);
}

//记忆化搜索的优化方式 利用map记录来优化
//map[i][j]表示递归process(arr,i,j,map)的返回值
int process2(vector<int>& arr, int level, int aim, vector<vector<int>>& map) {
    int res = 0;
    if (level == arr.size()) {
        return res = aim == 0 ? 1 : 0;
    }
    else {
        int mapValue = 0;
        for (int i = 0; i * arr[level] <= aim; i++) {
            //查询map中是否已经计算过 计算过不在递归
            mapValue = map[level + 1][aim - i * arr[level]];
            //mapValue ！= 0 表示计算过
            if (mapValue != 0) {
                res += mapValue == -1 ? 0 : mapValue;
            }
            else {
                //如果没计算过 就存储一下
                res += process2(arr, level + 1, aim - arr[level] * i, map);
            }
        }
    }    
    //存储本次的计算结果 判断是否有值
    map[level][aim] = res == 0 ? -1 : res;
    return res;
}

//
int coins3(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return 0;
    vector<vector<int>> dp(arr.size(), vector<int>(aim + 1));

    for (int i = 0; i < arr.size(); i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; arr[0] * i <= aim; i++) {
        dp[0][arr[0] * i] = 1;
    }
    int num = 0;
    for (int i = 1; i < arr.size(); i++) {
        for (int j = 1; j <= aim; j++) {
            num = 0;
            for (int k = 0; j - arr[i] * k >= 0; k++) {
                num += dp[i - 1][j - arr[i] * k];
            }
            dp[i][j] = num;
        }
    }
    return dp[arr.size() - 1][aim];
}

//
int coins5(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return 0;
    vector<int> dp(aim + 1);
    for (int i = 0; arr[0] * i <= aim; i++) {
        dp[arr[0] * i] = 1;
    }
    for (int i = 1; i < arr.size(); i++) {
        for (int j = 1; j <= aim; j++) {
            dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
        }
    }
    return dp[aim];
}
